package code;


public class MaximalRectangle {
	
    public int maximalRectangle(char[][] matrix) {
    	int n,m;
    	n=matrix.length;
    	if(n==0)	return 0;
    	m=matrix[0].length;
    	int[][] sum=new int[n+1][m+1];
    	int i,j;
    	for(i=0;i<n;i++){
    		for(j=0;j<m;j++)
    		{
    			sum[i+1][j+1]=sum[i][j+1]+sum[i+1][j]-sum[i][j];
    			if(matrix[i][j]=='1'){
    				sum[i+1][j+1]++;
    			}
    		}
    	}
    	int s,t;
    	int maxSum=0;
    	for(i=0;i<n;i++)
    		for(j=0;j<m;j++){
    			if(matrix[i][j]=='0')	continue;
    			for(s=i+1;s<n;s++)
    				for(t=j+1;t<m;t++){
    					if(maxSum<sum[s+1][t+1]-sum[i][j] && sum[s+1][t+1]-sum[i][j]==(s-i+1)*(t-j+1))
    						maxSum=sum[s+1][t+1]-sum[i][j];
    				}
    		}
    		
        return maxSum;
    }
    
	public static void main(String[] args){
		
	}
}
